package labuladong.第三章.滑动窗口;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Demo01 {

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        System.out.println(minWindow2(s, t));
    }

    public static String minWindow(String s, String t) {
        int minLength = Integer.MAX_VALUE;
        int front = 0;
        int end = 0;
        int sLength = s.length();
        int tLength = t.length();
        for(int i=0; i<sLength; i++) {
            for(int j=i+1; j<=sLength; j++) {
                String tempString = s.substring(i, j);
                int k;
                for(k=0; k<tLength; k++) {
                    if(!tempString.contains(t.charAt(k)+""))
                        break;
                }
                if(k == tLength && (j-i) < minLength) {
                    front = i;
                    end = j;
                    minLength = j-i;
                    break;
                }
            }
        }

        return s.substring(front, end);
    }

    public static String minWindow2(String s, String t) {
        // 遍历使用的指针
        int left = 0, right = 0;
        // 记录起点和符合要求的最短长度
        int start = 0, minLen = Integer.MAX_VALUE;
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();

        // 遍历时存储的map
        Map<Character, Integer> window = new HashMap<>();
        // 牧存储目标字符串的map
        Map<Character, Integer> needs = new HashMap<>();

        for(char c : tArr) {
            needs.put(c, needs.getOrDefault(c, 0) + 1);
        }

        // 遍历过程中匹配到的符合needs要求的次数
        int match = 0;

        while (right < sArr.length) {
            char c1 = sArr[right];
            // 如果needs包含此字符
            if(needs.containsKey(c1)) {
                // 记录在window中，并计数
                window.put(c1, window.getOrDefault(c1, 0) + 1);
                if(window.get(c1) == needs.get(c1)) {
                    match++;
                }
            }
            // 右移right
            right++;
            // 匹配次数等于needs中字符数开始left左移，直至不符合needs的要求
            while (match == needs.size()) {
                // 右移过程中，继续判断最短字符串
                if (right-left < minLen) {
                    start = left;
                    minLen = right - left;
                }
                char c2 = sArr[left];
                // 更新window
                if(needs.containsKey(c2)) {
                    if(window.get(c2) == 1) {
                        window.remove(c2);
                        match--;
                    } else {
                        window.put(c2, window.get(c2)-1);
                    }
                }
                // 右移left
                left ++;
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start+minLen);
    }
}
